﻿using System.Collections.Generic;
using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 杨辉三角
    {
        /// <summary>
        /// https://leetcode.cn/leetbook/read/top-interview-questions-easy/xncfnv/
        /// </summary>
        public class Solution
        {
            /// <summary>
            /// 2021-7-15
            /// 执行用时：192 ms, 在所有 C# 提交中击败了96.57%的用户
            /// 内存消耗：25.9 MB, 在所有 C# 提交中击败了51.45%的用户
            /// </summary>
            /// <param name="numRows"></param>
            /// <returns></returns>
            public IList<IList<int>> Generate(int numRows)
            {
                IList<IList<int>> result = new List<IList<int>>();
                for (var i = 0; i < numRows; i++)
                {
                    IList<int> rowResult = new List<int>();

                    for (var j = 0; j <= i; j++)
                    {
                        rowResult.Add(j == i || j == 0 ? 1 : result[i - 1][j - 1] + result[i - 1][j]);
                    }
                    result.Add(rowResult);
                }
                return result;
            }
        }

        ITestOutputHelper output;

        public 杨辉三角(ITestOutputHelper output)
        {
            this.output = output;
        }


        [Fact]
        public void Test1()
        {
            Solution solution = new Solution();
            var collection = solution.Generate(5);

            foreach (var items in collection)
            {
                output.WriteLine("" + string.Join(",", items));
            }

        }
    }
}
